package com.demo.function.arithmetic;

import com.alibaba.fastjson.JSON;
import lombok.extern.slf4j.Slf4j;

/**
 * 快速排序算法
 * @author cyj
 **/
@Slf4j
public class QuickSort {

    public void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            // 找出基准
            int partition = partition(arr, startIndex, endIndex);
            // 分两边递归进行
            quickSort(arr, startIndex, partition);
            quickSort(arr, partition + 1, endIndex);
        }
    }

    private int partition(int[] arr, int startIndex, int endIndex) {
        int pivot = arr[startIndex];

        int left = startIndex;
        int right = endIndex;

        while (left != right) {
            while (left < right && arr[right] > pivot) {
                right --;
            }

            while (left < right && arr[left] <= pivot) {
                left ++;
            }

            if (left < right) {
                swap(arr, left, right);
            }
        }

        swap(arr, startIndex, left);
        return left;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        log.info("数据排序：" + JSON.toJSONString(arr));
    }
}
